BM12 单链表的排序

BM12 单链表的排序

描述

给定一个节点数为n的无序单链表，对其按升序排序。 示例1 输入：[1,3,2,4,5] 返回值：5

归并排序

package main

import . "nc_tools"

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类 the head node
 * @return ListNode类
 */
func sortInList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	return sortFunc(head)

}
func sortFunc(head *ListNode) *ListNode {
	//终止条件
	if head.Next == nil {
		return head
	}

	//递
	var slow, fast *ListNode
	slow = head
	fast = head.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
     tmp:=slow.Next
     slow.Next = nil
	leftHead := sortFunc(head)
	rightHead := sortFunc(tmp)
	
	//归
	var newHead, nowNode *ListNode
	newHead = &ListNode{
		Val: 0,
	}
	nowNode = newHead

	for leftHead != nil && rightHead != nil {
		if leftHead.Val < rightHead.Val {
			nowNode.Next = leftHead
            leftHead=leftHead.Next
		} else {
			nowNode.Next = rightHead
            rightHead=rightHead.Next
		}
        nowNode=nowNode.Next
	}
    if leftHead==nil{
        nowNode.Next=rightHead
    }else{
        nowNode.Next=leftHead
    }
    

	newHead = newHead.Next

	return newHead

}

总结

之前已经遇到很多次，但还是没有一次写正确，主要还是卡在了临界条件的判断上。首先是终止条件是

if head.Next == nil {
		return head
	}

然后是进行划分时的临界判断和终止条件的判断

//终止条件
	if head.Next == nil {
		return head
	}
//划分判断	
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

这道题真是不应该了，下次不应在犯同样问题了。